package easy

import (
	. "GoLeetcode/common"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 1带1内部递归(带返回值)
func sumRootToLeaf(root *TreeNode) int {
	var dfs func(node *TreeNode, cur int) int
	dfs = func(node *TreeNode, cur int) int {
		if node == nil {
			return 0
		}
		cur = cur*2 + node.Val
		if isLeafNode(node) {
			return cur
		}
		return dfs(node.Left, cur) + dfs(node.Right, cur)
	}
	return dfs(root, 0)
}

// 1带1内部递归
func sumRootToLeaf1(root *TreeNode) int {
	var result int
	var dfs func(node *TreeNode, num int)
	dfs = func(node *TreeNode, num int) {
		if node != nil {
			// 计算根节点到当前节点构成的二进制数的值
			pathSum := num*2 + node.Val
			if isLeafNode(node) {
				result += pathSum
			} else {
				dfs(node.Left, pathSum)
				dfs(node.Right, pathSum)
			}
		}
	}
	dfs(root, 0)

	return result
}

// 判读是否是叶子节点
func isLeafNode(node *TreeNode) bool {
	return node.Right == nil && node.Left == nil
}
